{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "udacity-cs344-hw4",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/depctg/udacity-cs344-colab/blob/master/notebook/udacity_cs344_hw4.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "metadata": {
        "id": "hse6gSyUS5ka",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# Homework 4 for Udacity CS344 Course, Intro to Parallel Programming\n",
        "# clone the code repo,\n",
        "!git clone https://github.com/depctg/udacity-cs344-colab\n",
        "!pip install git+git://github.com/depctg/nvcc4jupyter.git\n",
        "\n",
        "# load cuda plugin\n",
        "%config NVCCPluginV2.static_dir = True\n",
        "%config NVCCPluginV2.relative_dir = \"udacity-cs344-colab/src/HW4\"\n",
        "%load_ext nvcc_plugin\n",
        "\n",
        "# change to work directory, generate makefiles\n",
        "!mkdir udacity-cs344-colab/build\n",
        "%cd udacity-cs344-colab/build\n",
        "!cmake ../src"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "3vA0JP15TORh",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "%%cuda --name student_func.cu\n",
        "\n",
        "//Udacity HW 4\n",
        "//Radix Sorting\n",
        "\n",
        "#include \"utils.h\"\n",
        "#include <thrust/host_vector.h>\n",
        "\n",
        "/* Red Eye Removal\n",
        "   ===============\n",
        "\n",
        "   For this assignment we are implementing red eye removal.  This is\n",
        "   accomplished by first creating a score for every pixel that tells us how\n",
        "   likely it is to be a red eye pixel.  We have already done this for you - you\n",
        "   are receiving the scores and need to sort them in ascending order so that we\n",
        "   know which pixels to alter to remove the red eye.\n",
        "\n",
        "   Note: ascending order == smallest to largest\n",
        "\n",
        "   Each score is associated with a position, when you sort the scores, you must\n",
        "   also move the positions accordingly.\n",
        "\n",
        "   Implementing Parallel Radix Sort with CUDA\n",
        "   ==========================================\n",
        "\n",
        "   The basic idea is to construct a histogram on each pass of how many of each\n",
        "   \"digit\" there are.   Then we scan this histogram so that we know where to put\n",
        "   the output of each digit.  For example, the first 1 must come after all the\n",
        "   0s so we have to know how many 0s there are to be able to start moving 1s\n",
        "   into the correct position.\n",
        "\n",
        "   1) Histogram of the number of occurrences of each digit\n",
        "   2) Exclusive Prefix Sum of Histogram\n",
        "   3) Determine relative offset of each digit\n",
        "        For example [0 0 1 1 0 0 1]\n",
        "                ->  [0 1 0 1 2 3 2]\n",
        "   4) Combine the results of steps 2 & 3 to determine the final\n",
        "      output location for each element and move it there\n",
        "\n",
        "   LSB Radix sort is an out-of-place sort and you will need to ping-pong values\n",
        "   between the input and output buffers we have provided.  Make sure the final\n",
        "   sorted results end up in the output buffer!  Hint: You may need to do a copy\n",
        "   at the end.\n",
        "\n",
        " */\n",
        "\n",
        "\n",
        "void your_sort(unsigned int* const d_inputVals,\n",
        "               unsigned int* const d_inputPos,\n",
        "               unsigned int* const d_outputVals,\n",
        "               unsigned int* const d_outputPos,\n",
        "               const size_t numElems)\n",
        "{\n",
        "  //TODO\n",
        "  //PUT YOUR SORT HERE\n",
        "}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "sSAnpiE2nL1T",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# make the cuda project\n",
        "!make HW4\n",
        "print(\"\\n====== RESULT OF HW4 =======\\n\")\n",
        "!bin/HW4 ../src/HW4/red_eye_effect.gold ../src/HW4/red_eye_effect_template_5.jpg"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "2cGKiWj_n-Na",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        "# plot output images\n",
        "import matplotlib.pyplot as plt\n",
        "_,ax = plt.subplots(1,2, dpi=150)\n",
        "\n",
        "ax[0].imshow(plt.imread(\"../src/HW4/red_eye_effect_5.jpg\"))\n",
        "ax[0].set_title(\"original\")\n",
        "ax[0].grid(False)\n",
        "\n",
        "ax[1].imshow(plt.imread(\"HW4_output.png\"))\n",
        "ax[1].set_title(\"output\")\n",
        "ax[1].grid(False)\n",
        "\n",
        "plt.show()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "metadata": {
        "id": "E7PIZcQmuKP9",
        "colab_type": "code",
        "colab": {}
      },
      "cell_type": "code",
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}